package uestc.lj.midPromotion.dfs;

/**
 * 递归公式套路
 *
 * @Author:Crazlee
 * @Date:2021/12/2
 */
public class Code07_Fibonacci {
	public static int fibonacci1(int n) {
		if (n < 1) {
			return 0;
		}
		return process(1, n);
	}

	private static int process(int i, int n) {
		if (i == n - 1) {
			return 2;
		}
		if (i == n) {
			return 1;
		}
		return process(i + 1, n) + process(i + 2, n);
	}

	public static int fibonacci2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		int pre = 1;
		int cur = 1;
		int temp = 0;
		for (int i = 2; i <= n; i++) {
			temp = cur;
			cur += pre;
			pre = temp;
		}
		return cur;
	}

	/**
	 * 利用行列式矩阵求解递归公式套路
	 *
	 * @param n
	 * @return
	 */
	public static int fibonacci3(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return n;
		}
		int[][] base = {{1, 1}, {1, 0}};
		int[][] res = matrixPower(base, n - 2);
		return 2 * res[0][0] + res[1][0];
	}

	/**
	 * 矩阵m的p次方
	 *
	 * @param m
	 * @param p
	 * @return
	 */
	private static int[][] matrixPower(int[][] m, int p) {
		int[][] res = new int[m.length][m[0].length];
		for (int i = 0; i < res.length; i++) {
			res[i][i] = 1;
		}
		int[][] t = m;
		for (; p != 0; p >>= 1) {
			if ((p & 1) != 0) {
				res = muliMatrix(res, t);
			}
			t = muliMatrix(t, t);
		}
		return res;
	}

	/**
	 * 两个矩阵相乘
	 *
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	private static int[][] muliMatrix(int[][] arr1, int[][] arr2) {
		int[][] res = new int[arr1.length][arr2[0].length];
		for (int i = 0; i < arr1.length; i++) {
			for (int j = 0; j < arr2[0].length; j++) {
				for (int k = 0; k < arr2.length; k++) {
					res[i][j] += arr1[i][k] * arr2[k][j];
				}
			}
		}
		return res;
	}

	public static void main(String[] args) {
		for (int i = 0; i != 20; i++) {
			System.out.println(fibonacci1(i));
			System.out.println(fibonacci2(i));
			System.out.println(fibonacci3(i));
			System.out.println("===================");
		}

	}
}
